/**************************************************************************
* File:            tarjan.h	                                              *
* Description:	   Tarjan algorithm (strongly-connected components)       *
* Author:          Zhuk Artsem, 399                                       *
**************************************************************************/

#pragma once

#include "graph.h"
#include "search.h"
#include <stack>
#include <vector>

class TarjanRunner :public Visitor{ 
	std::stack<int> stack_;
	int time_;
	std::vector<int> time_in_;
	std::vector<int> low_link_;
	std::vector<bool> in_stack_;
	std::vector<bool> visited_;
	std::vector<std::vector<int>> components_;
	void addComponent(int head_vertex){
		components_.push_back(std::vector<int>());
		int last = -1;
		while (last!=head_vertex){
			last = stack_.top();
			in_stack_[last] = false;
			components_.back().push_back(last);
			stack_.pop();
		}
	}
public:
	TarjanRunner() :time_(0){}

	void setGraphSize(int vertices_number){
		time_in_.resize(vertices_number);
		low_link_.resize(vertices_number);
		in_stack_.resize(vertices_number);
		visited_.resize(vertices_number);
	}

	void enterVertex(int vertex){
		stack_.push(vertex);
		time_in_[vertex] = low_link_[vertex] = time_++;
		in_stack_[vertex] = true;
		visited_[vertex] = true;
	}

	void enterEdge(int from, int to){
		if (visited_[to] && in_stack_[to])
		low_link_[from] = std::min(low_link_[from], time_in_[to]);
	}

	void leaveEdge(int from, int to){
		low_link_[from] = std::min(low_link_[from], low_link_[to]);
	}

	void leaveVertex(int vertex){
		if (time_in_[vertex] == low_link_[vertex])
			addComponent(vertex);
	}

	std::vector<std::vector<int>> getComponents(){
		return components_;
	}

	void reset(){
		time_ = 0;
		components_.clear();
		time_in_.clear();
		low_link_.clear();
		visited_.clear();
		in_stack_.clear();
		while (!stack_.empty()){
			stack_.pop();
		}
	}
};

std::vector<std::vector<int> > getSCC(Graph const * graph){
	TarjanRunner tarjanRunner;

	tarjanRunner.setGraphSize(graph->getVerticesNumber());

	runDFS(graph, &tarjanRunner);

	return tarjanRunner.getComponents();
}